import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Stack;
import java.util.TreeMap;


public class Ex5_3 {


	public Ex5_3() {}

	public static void main(String[] args) {

		Ex5_3 exe = new Ex5_3();
		ArrayList<String> combinations = exe.generateCombinations(4);
		TreeMap<String,ArrayList<String>> graphOut 
								= exe.generateGraphOut(combinations);
		ArrayList<String> cycle = exe.eulerCycle(graphOut);
		System.out.println(cycle);

	}


	private ArrayList<String> getCycle(
			TreeMap<String,ArrayList<String>> outGraph, String node) {
		// used edges
		ArrayList<String> usedEdges = new ArrayList<String>();
		ArrayList<String> nodes = new ArrayList<String>();
		String currentNode = node;
		boolean hasNonUsedEdges;
		do {
			hasNonUsedEdges = false;
			nodes.add(currentNode);
			ArrayList<String> outgoings = outGraph.get(currentNode);
			for (String outgoing : outgoings) {
				String edge = currentNode + "_" + outgoing;
				if (!usedEdges.contains(edge)) {
					usedEdges.add(edge);
					currentNode = outgoing;
					hasNonUsedEdges = true;
					break;					
				}				
			}
		} while(hasNonUsedEdges);
		return nodes;
	}

	private String getUnexplored(ArrayList<String> cycle,
			TreeMap<String,ArrayList<String>> outGraph) {

		String finalnode = null;
		HashMap<String,ArrayList<String>> cycleGraph = 
				new HashMap<String,ArrayList<String>>();
		for (int i=0;i<cycle.size()-1;i++) {
			String origin = cycle.get(i);
			String destiny = cycle.get(i+1);
			ArrayList<String> outgoings = cycleGraph.get(origin);
			if (outgoings == null) {
				outgoings = new ArrayList<String>();
				outgoings.add(destiny);
				cycleGraph.put(origin, outgoings);
			} else {
				outgoings.add(destiny);
			}
		}

		for (String node : cycle) {
			Integer nOutcycle = cycleGraph.get(node).size();
			Integer nOutgraph = outGraph.get(node).size();
			if (nOutcycle < nOutgraph) {
				finalnode = node;
				break;
			}
		}


		return finalnode;
	}

	//EULERIANCYCLE(Graph)
	//form a cycle Cycle by randomly walking in Graph (never visit an edge twice!)
	//while there are unexplored edges
	//    select a node newStart in Cycle with still unexplored edges
	//    form Cycle’ by traversing Cycle (starting at newStart) and randomly walking 
	//    Cycle ← Cycle’
	//return Cycle
	private ArrayList<String> eulerCycle(TreeMap<String,ArrayList<String>> outGraph) {
		ArrayList<String> cycle = getCycle(outGraph, "000");
		String newStart = null;
		do {
			newStart = getUnexplored(cycle, outGraph);
			if (newStart != null) {
				cycle = getCycle(outGraph, newStart); 
			}
		} while (newStart != null);
		return cycle;
	}


	private Integer random(Integer min, Integer max) {
		return min + (int)(Math.random() * ((max - min) + 1));		
	}

	private TreeMap<String,ArrayList<String>> 
						generateGraphOut(ArrayList<String> kmers) {
		TreeMap<String,ArrayList<String>> graph = 
				new TreeMap<String,ArrayList<String>> ();  
		for (String kmer : kmers) {
			String prefix = kmer.substring(0,kmer.length()-1);
			String sufix = kmer.substring(1,kmer.length());
			ArrayList<String> outgoings = graph.get(prefix);
			if (outgoings == null) {
				outgoings = new ArrayList<String>();
				outgoings.add(sufix);
				graph.put(prefix, outgoings);
			} else {
				if (!outgoings.contains(sufix)) {
					outgoings.add(sufix);
				}
			}

		}
		return graph;
	}


	private ArrayList<String> generateCombinations(Integer k) {
		char[] symbols = {'0','1'};
		Integer m = symbols.length;
		ArrayList<String> list = new ArrayList<String>();
		for (int i=1;i<= Math.pow(m, k);i++) {
			String kmer = "";
			for (int j=0;j<k;j++) {
				Integer n = (i /  
						Double.valueOf(Math.pow(m, j)).intValue()) % m;
				kmer = kmer + symbols[n];
			}
			list.add(kmer);
		}		

		return list;
	}

}
